//
// Description: 740. 删除并获得点数
// Created by Loading on 2022/6/17.
//

#include <bits/stdc++.h>

using namespace std;

int deleteAndEarn(vector<int> &nums) {
    unordered_map<int, int> cnt;
    for (auto &x : nums) {
        cnt[x]++;
    }

    vector<int> vec;
    for (auto[k, v] : cnt) {
        vec.emplace_back(k);
    }
    sort(vec.begin(), vec.end());
    int n = vec.size();

    /* 线性DP */
    // dp[i][0] 表示 0~i 且不选 i 获得的最大点数
    // dp[i][1] 表示 0~i 且选 i 获得的最大点数
    int dp[n][2];
    memset(dp, 0, sizeof dp);
    dp[0][1] = vec[0] * cnt[vec[0]];
    for (int i = 1; i < n; ++i) {
        // 不选择 i，则使用 前一个选择和不选择 的最大值转移
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
        // 选择 i，则不能选择 vec[i] - 1 的值
        if (vec[i] - 1 == vec[i - 1]) {
            dp[i][1] = dp[i - 1][0] + cnt[vec[i]] * vec[i];
        } else {
            dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]) + cnt[vec[i]] * vec[i];
        }
    }

    return max(dp[n - 1][0], dp[n - 1][1]);
}

int main() {
    vector<int> nums{2, 2, 3, 3, 3, 4};

    auto res = deleteAndEarn(nums);

    cout << res << endl;

    return 0;
}